home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / cuj0593.zip / 1105035A < prev    next >
Text File  |  1993-03-04  |  15KB  |  767 lines
  1. // ==================================================================
  2. // btree.h
  3. //    Template-based balanced binary tree class.
  4. //    Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.
  5. // ==================================================================
  6.  
  7. #ifndef __BTREE__
  8.  
  9. #define __BTREE__
  10.  
  11. // BinaryNode is the class template that does all the work.
  12. // All the binary tree primitives are implemented in here.
  13. template<class T>
  14. class BinaryNode {
  15. protected:
  16.     // For node colors
  17.     enum RedBlack { Black, Red };
  18. public:
  19.     T x;                // Node contents
  20.     enum RedBlack clr;            // Color of node (red or black)
  21.     BinaryNode<T> *l, *r, *p;        // Left, right and parent pointers
  22.  
  23. protected:
  24.     // Tree manipulations used during insertion and deletion
  25.     virtual BinaryNode<T> *LeftRotate(BinaryNode<T> *root);
  26.     virtual BinaryNode<T> *RightRotate(BinaryNode<T> *root);
  27.     virtual BinaryNode<T> *DeleteFixup(BinaryNode<T> *x, BinaryNode<T> *p);
  28.  
  29. public:
  30.     // Constructors.  Node always starts out red.
  31.     BinaryNode();
  32.     BinaryNode(const T& X, BinaryNode<T> *P = 0, 
  33.     BinaryNode<T> *L = 0, BinaryNode<T> *R = 0);
  34.     virtual ~BinaryNode() { }
  35.     static void PostOrderDeletion(BinaryNode<T> *r);
  36.     virtual BinaryNode<T> *Dup(BinaryNode<T> *P) const;
  37.  
  38.     // Operations defined on binary trees.  All run in O(lgN) time.
  39.     virtual BinaryNode<T> *Min();
  40.     virtual BinaryNode<T> *Max();
  41.     virtual BinaryNode<T> *Pred();
  42.     virtual BinaryNode<T> *Succ();
  43.     virtual BinaryNode<T> *Query(const T& q);
  44.     virtual BinaryNode<T> *InsertNode(BinaryNode<T> *root);
  45.     virtual BinaryNode<T> *Insert(const T& AddMe);
  46.     virtual BinaryNode<T> *DeleteNode(BinaryNode<T> *z);
  47.     virtual BinaryNode<T> *DeleteItem(const T& q);
  48.     virtual BinaryNode<T> *DeletePassbk(T q, T *passbk);
  49.  
  50.     // Returns 0 if the red-black invariant holds.
  51.     virtual int CheckInvariant(int i, int num);
  52.  
  53.     // Returns number of black nodes from root to leftmost node.
  54.     int BlackToMin();
  55. };
  56.  
  57.  
  58. template<class T>
  59. class BinaryTreeIter {
  60. public:
  61.     // Create iterator for tree, initially pointing at root.
  62.     BinaryTreeIter(BinaryTree<T>& tree);
  63.  
  64.     // Create iterator for tree, initially pointing at the node
  65.     // queried by q.
  66.     BinaryTreeIter(BinaryTree<T>& tree, const T& q);
  67.  
  68.     // Reset iterator to point to root of given tree.
  69.     void Reset(BinaryTree<T>& tree);
  70.  
  71.     // Returns pointer to the contents of the current node, or
  72.     // 0 if the current node is 0.
  73.     T *Contents() const;
  74.  
  75.     // Sets iterator to point to minimum node in the subtree.
  76.     void Min();
  77.  
  78.     // Sets iterator to point to maximum node in the subtree.
  79.     void Max();
  80.  
  81.     // Sets iterator to point to the current node's predecessor.
  82.     void Pred();
  83.  
  84.     // Sets iterator to point to the current node's successor.
  85.     void Succ();
  86.  
  87.     // Queries subtree for the given key.
  88.     int Query(const T&);
  89.  
  90. protected:
  91.     BinaryTree<T> *tree;    // Pointer to the tree being scanned
  92.  
  93.     BinaryNode<T> *subtree;    // Subtree currently being considered
  94. };
  95.  
  96. // BinaryTree class template.
  97. template<class T> 
  98. class BinaryTree {
  99.  
  100. protected:
  101.     BinaryNode<T> *root;
  102.  
  103. public:
  104.     // Default constructor.
  105.     BinaryTree();
  106.  
  107.     // Copy constructor.
  108.     BinaryTree(const BinaryTree<T>& x);
  109.  
  110.     // Assignment operator.
  111.     BinaryTree<T>& operator= (const BinaryTree<T>& x);
  112.  
  113.     // Destructor.
  114.     ~BinaryTree();
  115.  
  116.     virtual T *Min() const;
  117.     virtual T *Max() const;
  118.     virtual T *Pred(const T& q) const;
  119.     virtual T *Succ(const T& q) const;
  120.     virtual T *Query(const T& q) const;
  121.     virtual void Insert(const T& addme);
  122.     virtual void DeleteItem(const T& q);
  123.     virtual void DeletePassbk(const T& q, T *passbk);
  124.     virtual int IsEmpty() const;
  125.     virtual int CheckInvariant();
  126.  
  127. // The following are accessible only to classes that inherit
  128. // from BinaryTree, since they deal directly with BinaryNodes.
  129. protected:
  130.     virtual BinaryNode<T> *InsertPassbk(const T& addme);
  131.     virtual BinaryNode<T> *QueryNode(const T& q) const;
  132.     virtual void DeleteNode(BinaryNode<T> *delme);
  133.  
  134.     friend BinaryTreeIter<T>;
  135. };
  136.  
  137. template<class T>
  138. BinaryTreeIter<T>::BinaryTreeIter(BinaryTree<T>& Tree)
  139. {
  140.     tree = &Tree;
  141.     subtree = tree->root;
  142. }
  143.  
  144. template<class T>
  145. BinaryTreeIter<T>::BinaryTreeIter(BinaryTree<T>& Tree, const T& q)
  146. {
  147.     tree = &Tree;
  148.     subtree = tree->root;
  149.     if (subtree)
  150.     subtree = subtree->Query(q);
  151. }
  152.  
  153. template<class T>
  154. void
  155. BinaryTreeIter<T>::Reset(BinaryTree<T>& Tree)
  156. {
  157.     tree = &Tree;
  158.     subtree = tree->root;
  159. }
  160.  
  161. template<class T>
  162. T *
  163. BinaryTreeIter<T>::Contents() const
  164. {
  165.     return (subtree) ? &subtree->x : 0;
  166. }
  167.  
  168. template<class T>
  169. void
  170. BinaryTreeIter<T>::Min()
  171. {
  172.     if (subtree)
  173.     subtree = subtree->Min();
  174. }
  175.  
  176. template<class T>
  177. void
  178. BinaryTreeIter<T>::Max()
  179. {
  180.     if (subtree)
  181.     subtree = subtree->Max();
  182. }
  183.  
  184. template<class T>
  185. void
  186. BinaryTreeIter<T>::Pred()
  187. {
  188.     if (subtree)
  189.     subtree = subtree->Pred();
  190. }
  191.  
  192. template<class T>
  193. void
  194. BinaryTreeIter<T>::Succ()
  195. {
  196.     if (subtree)
  197.     subtree = subtree->Succ();
  198. }
  199.  
  200. template<class T>
  201. int
  202. BinaryTreeIter<T>::Query(const T& x)
  203. {
  204.     subtree = (subtree) ? subtree->Query(x) : 0;
  205.     return subtree != 0;
  206. }
  207.  
  208.     // Private enum to implement the red-black tree.
  209. //    enum RedBlack { Black, Red };
  210.  
  211. template<class T>
  212. BinaryTree<T>::BinaryTree()
  213. {
  214.     root = 0;
  215. }
  216.  
  217. template<class T>
  218. BinaryTree<T>::BinaryTree(const BinaryTree<T>& x)
  219. {
  220.     root = x.root->Dup(0);
  221. }
  222.  
  223. template<class T>
  224. BinaryTree<T>&
  225. BinaryTree<T>::operator=(const BinaryTree<T>& x)
  226. {
  227.     BinaryNode<T>::PostOrderDeletion(root);
  228.     root = x.root->Dup(0);
  229.     return *this;
  230. }
  231.  
  232. template<class T>
  233. BinaryTree<T>::~BinaryTree()
  234. {
  235.     BinaryNode<T>::PostOrderDeletion(root);
  236. }
  237.  
  238. template<class T>
  239. T *
  240. BinaryTree<T>::Min() const
  241. {
  242.     return (root) ? &root->Min()->x : 0;
  243. }
  244.  
  245. template<class T>
  246. T *
  247. BinaryTree<T>::Max() const
  248. {
  249.     return (root) ? &root->Max()->x : 0;
  250. }
  251.  
  252. template<class T>
  253. T *
  254. BinaryTree<T>::Pred(const T& q) const
  255. {
  256.     BinaryNode<T> *p = (root) ? root->Query(q) : 0;
  257.     if (p) {
  258.         BinaryNode<T> *r = p->Pred();
  259.         return (r) ? &r->x : 0;
  260.     }
  261.     else return 0;
  262. }
  263.  
  264. template<class T>
  265. T *
  266. BinaryTree<T>::Succ(const T& q) const
  267. {
  268.     BinaryNode<T> *p = (root) ? root->Query(q) : 0;
  269.     if (p) {
  270.         BinaryNode<T> *r = p->Succ();
  271.         return (r) ? &r->x : 0;
  272.     }
  273.     else return 0;
  274. }
  275.  
  276. template<class T>
  277. T *
  278. BinaryTree<T>::Query(const T& q) const
  279. {
  280.     BinaryNode<T> *p = (root) ? root->Query(q) : 0;
  281.     return (p) ? &p->x : 0;
  282. }
  283.  
  284. template<class T>
  285. void
  286. BinaryTree<T>::Insert(const T& addme)
  287. {
  288.     if (root)
  289.     root = root->Insert(addme);
  290.     else
  291.     root = new BinaryNode<T>(addme);
  292. }
  293.  
  294. template<class T>
  295. BinaryNode<T> *
  296. BinaryTree<T>::InsertPassbk(const T& addme)
  297. {
  298.     if (root)
  299.         root = root->Insert(addme);
  300.     else
  301.         root = new BinaryNode<T>(addme);
  302.     return root->Query(addme);
  303. }
  304.  
  305. template<class T>
  306. void
  307. BinaryTree<T>::DeleteItem(const T& q)
  308. {
  309.     if (root)
  310.     root = root->DeleteItem(q);
  311. }
  312.  
  313. template<class T>
  314. void
  315. BinaryTree<T>::DeletePassbk(const T& q, T *passbk)
  316. {
  317.     if (root)
  318.         root = root->DeletePassbk(q, passbk);
  319. }
  320.  
  321. template<class T>
  322. int
  323. BinaryTree<T>::IsEmpty() const
  324. {
  325.     return root == 0;
  326. }
  327.  
  328. template<class T>
  329. int
  330. BinaryTree<T>::CheckInvariant()
  331. {
  332.     return (root) ? root->CheckInvariant(0, root->BlackToMin()) : 0;
  333. }
  334.  
  335. template<class T>
  336. BinaryNode<T> *
  337. BinaryTree<T>::QueryNode(const T& q) const
  338. {
  339.     return (root) ? root->Query(q) : 0;
  340. }
  341.  
  342. template<class T>
  343. void
  344. BinaryTree<T>::DeleteNode(BinaryNode<T> *delme)
  345. {
  346.     if (root)
  347.     root = root->DeleteNode(delme);
  348. }
  349.  
  350. template<class T>
  351. BinaryNode<T>::BinaryNode()
  352. {
  353.     clr = Red;
  354.     l = r = p = 0;
  355. }
  356.  
  357. template<class T>
  358. BinaryNode<T>::BinaryNode(const T& X, BinaryNode<T> *P = 0,
  359.     BinaryNode<T> *L = 0, BinaryNode<T> *R = 0): x(X)
  360. {
  361.     clr = Red;
  362.     p = P;
  363.     l = L;
  364.     r = R;
  365. }
  366.  
  367. template<class T>
  368. void
  369. BinaryNode<T>::PostOrderDeletion(BinaryNode<T> *r)
  370. {
  371.     if (r) {
  372.         PostOrderDeletion(r->l);
  373.         PostOrderDeletion(r->r);
  374.         delete r;
  375.     }
  376. }
  377.  
  378. template<class T>
  379. BinaryNode<T> *
  380. BinaryNode<T>::Dup(BinaryNode<T> *P) const
  381. {
  382.     BinaryNode<T> *ret = new BinaryNode<T>(x);
  383.     ret->clr = clr;
  384.     ret->l = l->Dup(ret);
  385.     ret->r = r->Dup(ret);
  386.     ret->p = P;
  387.     return ret;
  388. }
  389.  
  390. template<class T>
  391. BinaryNode<T> *
  392. BinaryNode<T>::Min()
  393. {
  394.     BinaryNode<T> *x = this;
  395.     while (x && x->l)
  396.         x = x->l;
  397.     return x;
  398. }
  399.  
  400. template<class T>
  401. BinaryNode<T> *
  402. BinaryNode<T>::Max()
  403. {
  404.     BinaryNode<T> *x = this;
  405.     while (x && x->r)
  406.         x = x->r;
  407.     return x;
  408. }
  409.  
  410. template<class T> 
  411. BinaryNode<T> *
  412. BinaryNode<T>::Min()
  413. {
  414.     BinaryNode<T> *x = this;
  415.     while (x && x->l)
  416.     x = x->l;
  417.     return x;
  418. }
  419.  
  420. template<class T> 
  421. BinaryNode<T> *
  422. BinaryNode<T>::Max()
  423. {
  424.     BinaryNode<T> *x = this;
  425.     while (x && x->r)
  426.     x = x->r;
  427.     return x;
  428. }
  429.  
  430. template<class T> 
  431. BinaryNode<T> *
  432. BinaryNode<T>::Pred()
  433. {
  434.     BinaryNode<T> *trav = this;
  435.     if (trav->l)
  436.     return trav->l->Max();
  437.     BinaryNode<T> *y = trav->p;
  438.     while (y && trav == y->l) {
  439.     trav = y;
  440.     y = y->p;
  441.     }
  442.     return y;
  443. }
  444.  
  445. template<class T> 
  446. BinaryNode<T> *
  447. BinaryNode<T>::Succ()
  448. {
  449.     BinaryNode<T> *trav = this;
  450.     if (trav->r)
  451.     return trav->r->Min();
  452.     BinaryNode<T> *y = trav->p;
  453.     while (y && trav == y->r) {
  454.     trav = y;
  455.     y = y->p;
  456.     }
  457.     return y;
  458. }
  459.  
  460. template<class T> 
  461. BinaryNode<T> *
  462. BinaryNode<T>::Query(const T& q)
  463. {
  464.     BinaryNode<T> *trav = this;
  465.     while (trav) {
  466.     if (q < trav->x)
  467.         trav = trav->l;
  468.     else if (trav->x < q)
  469.         trav = trav->r;
  470.     else
  471.         return trav;
  472.     }
  473.     return 0;
  474. }
  475.  
  476. template<class T> 
  477. BinaryNode<T> *
  478. BinaryNode<T>::LeftRotate(BinaryNode<T> *root)
  479. {
  480.     BinaryNode<T> *ret = root;
  481.     BinaryNode<T> *y = r;
  482.     r = y->l;
  483.     if (r)
  484.     r->p = this;
  485.     y->p = p;
  486.     if (p) {
  487.     if (this == p->l)
  488.         p->l = y;
  489.     else
  490.         p->r = y;
  491.     }
  492.     else
  493.     ret = y;
  494.     y->l = this;
  495.     p = y;
  496.     return ret;
  497. }
  498.  
  499. template<class T> 
  500. BinaryNode<T> *
  501. BinaryNode<T>::RightRotate(BinaryNode<T> *root)
  502. {
  503.     BinaryNode<T> *ret = root;
  504.     BinaryNode<T> *x = l;
  505.     l = x->r;
  506.     if (l)
  507.     l->p = this;
  508.     x->p = p;
  509.     if (p) {
  510.     if (this == p->l)
  511.         p->l = x;
  512.     else
  513.         p->r = x;
  514.     }
  515.     else
  516.     ret = x;
  517.     x->r = this;
  518.     p = x;
  519.     return ret;
  520. }
  521.  
  522. template<class T>
  523. BinaryNode<T> *
  524. BinaryNode<T>::InsertNode(BinaryNode<T> *addme)
  525. {
  526.     BinaryNode<T> *root = this;
  527.     if (! addme->p)
  528.     root = addme;
  529.     else {
  530.     if (addme->x < addme->p->x)
  531.         addme->p->l = addme;
  532.     else
  533.         addme->p->r = addme;
  534.     }
  535.     clr = Red;
  536.     while (addme != root && addme->p->clr == Red) {
  537.     BinaryNode<T> *y;
  538.  
  539.     if (! addme->p->p)
  540.         break;
  541.     if (addme->p == addme->p->p->l) {
  542.         y = addme->p->p->r;
  543.         if (y && y->clr == Red) {
  544.         addme->p->clr = Black;
  545.         y->clr = Black;
  546.         addme->p->p->clr = Red;
  547.         addme = addme->p->p;
  548.         }
  549.         else {
  550.         if (addme == addme->p->r) {
  551.             addme = addme->p;
  552.             root = addme->LeftRotate(root);
  553.         }
  554.             addme->p->clr = Black;
  555.             if (addme->p->p) {
  556.             addme->p->p->clr = Red;
  557.             root = addme->p->p->RightRotate(root);
  558.         }
  559.         }
  560.     }
  561.     else {
  562.         y = addme->p->p->l;
  563.         if (y && y->clr == Red) {
  564.         addme->p->clr = Black;
  565.         y->clr = Black;
  566.         addme->p->p->clr = Red;
  567.         addme = addme->p->p;
  568.         }
  569.         else {
  570.         if (addme == addme->p->l) {
  571.             addme = addme->p;
  572.             root = addme->RightRotate(root);
  573.         }
  574.         addme->p->clr = Black;
  575.         if (addme->p->p) {
  576.             addme->p->p->clr = Red;
  577.             root = addme->p->p->LeftRotate(root);
  578.         }
  579.         }
  580.     }
  581.     }
  582.     root->clr = Black;
  583.     return root;
  584. }
  585.  
  586. template<class T> 
  587. BinaryNode<T> *
  588. BinaryNode<T>::Insert(const T& AddMe)
  589. {
  590.     BinaryNode<T> *x = this;
  591.     BinaryNode<T> *y = 0;
  592.     while (x) {
  593.     y = x;
  594.     x = (AddMe < x->x) ? x->l : x->r;
  595.     }
  596.     BinaryNode<T> *addme = new BinaryNode<T>(AddMe, y);
  597.     return InsertNode(addme);
  598. }
  599.  
  600. template<class T> 
  601. BinaryNode<T> *
  602. BinaryNode<T>::DeleteFixup(BinaryNode<T> *x, BinaryNode<T> *p)
  603. {
  604.     BinaryNode<T> *root = this;
  605.     while (x != root && (! x || x->clr == Black)) {
  606.     BinaryNode<T> *w;
  607.     if (x == p->l) {
  608.         if (! p)
  609.         return root;
  610.         w = p->r;
  611.         if (! w)
  612.         return root;
  613.         if (w->clr == Red) {
  614.         w->clr = Black;
  615.         p->clr = Red;
  616.         root = p->LeftRotate(root);
  617.         w = p->r;
  618.         if (! p || ! w)
  619.             return root;
  620.         }
  621.         if ( ((! w->l) || w->l->clr == Black) &&
  622.          ((! w->r) || w->r->clr == Black)) {
  623.         w->clr = Red;
  624.         x = p;
  625.         p = p->p;
  626.         continue;
  627.         }
  628.         else if ((! w->r) || w->r->clr == Black) {
  629.         w->l->clr = Black;
  630.         w->clr = Red;
  631.         root = w->RightRotate(root);
  632.         w = p->r;
  633.         if (! p || ! w)
  634.             return root;
  635.         }
  636.         w->clr = p->clr;
  637.         if (p)
  638.         p->clr = Black;
  639.         w->r->clr = Black;
  640.         if (p)
  641.         root = p->LeftRotate(root);
  642.         x = root;
  643.       }
  644.     else {
  645.         if (! p)
  646.         return root;
  647.         w = p->l;
  648.         if (! p || ! w)
  649.         return root;
  650.         if (w->clr == Red) {
  651.         w->clr = Black;
  652.         p->clr = Red;
  653.         root = p->RightRotate(root);
  654.         w = p->l;
  655.         if (! p || ! w)
  656.             return root;
  657.         }
  658.         if ( ((! w->r) || w->r->clr == Black) &&
  659.              ((! w->l) || w->l->clr == Black)) {
  660.         w->clr = Red;
  661.         x = p;
  662.         p = p->p;
  663.         continue;
  664.         }
  665.         else if ((! w->l) || w->l->clr == Black) {
  666.         w->r->clr = Black;
  667.         w->clr = Red;
  668.         root = w->LeftRotate(root);
  669.         w = p->l;
  670.         if (! p || ! w)
  671.             return root;
  672.         }
  673.         w->clr = p->clr;
  674.         if (p)
  675.         p->clr = Black;
  676.         w->l->clr = Black;
  677.         if (p)
  678.         root = p->RightRotate(root);
  679.         x = root;
  680.     }
  681.     }
  682.     if (x)
  683.     x->clr = Black;
  684.     return root;
  685. }
  686.  
  687. template<class T> 
  688. BinaryNode<T> *
  689. BinaryNode<T>::DeleteNode(BinaryNode<T> *z)
  690. {
  691.     BinaryNode<T> *root = this;
  692.     BinaryNode<T> *x, *y;
  693.  
  694.     if (! z)
  695.     return root;
  696.     y = (! z->l || ! z->r) ? z : z->Succ();
  697.     x = (y->l) ? y->l : y->r;
  698.  
  699.     if (x)
  700.     x->p = y->p;
  701.  
  702.     if (y->p) {
  703.     if (y == y->p->l)
  704.         y->p->l = x;
  705.     else
  706.         y->p->r = x;
  707.     }
  708.     else
  709.     root = x;
  710.     if (y != z)
  711.     z->x = y->x;
  712.     if (y->clr == Black) {
  713.     if (root)
  714.         root = root->DeleteFixup(x, y->p);
  715.     }
  716.     delete y;
  717.     return root;
  718. }
  719.  
  720. template<class T> 
  721. BinaryNode<T> *
  722. BinaryNode<T>::DeleteItem(const T& q)
  723. {
  724.     return DeleteNode(Query(q));
  725. }
  726.  
  727. template<class T> 
  728. BinaryNode<T> *
  729. BinaryNode<T>::DeletePassbk(T q, T *passbk)
  730. {
  731.     BinaryNode<T> *z = Query(q);
  732.     if (z)
  733.     *passbk = z->x;
  734.     return DeleteNode(z);
  735. }
  736.  
  737. template<class T> 
  738. int
  739. BinaryNode<T>::CheckInvariant(int i, int num)
  740. {
  741.     int ret;
  742.     if (! l && (i != num + clr == Black))
  743.     return -1;
  744.     if (! r && (i != num + clr == Black))
  745.     return -1;
  746.     ret = (l) ? l->CheckInvariant(i + (clr == Black), num) : 0;
  747.     if (ret)
  748.     return ret;
  749.     return r && r->CheckInvariant(i + (clr == Black), num);
  750. }
  751.  
  752. template<class T> 
  753. int
  754. BinaryNode<T>::BlackToMin()
  755. {
  756.     BinaryNode<T> *trav = this;
  757.     int ret = 0;
  758.     while (trav) {
  759.     ret += (trav->clr == Black);
  760.     trav = trav->l;
  761.     }
  762.     return ret;
  763. }
  764.  
  765. #endif
  766.  
  767.